//题目:
// 给你一个字符串s,找到s中最长的回文子串。

#include<iostream>
#include<string>

using namespace std;
//代码：
class Solution 
{
public:
    bool is_reverse(char* left,char* right)
    {
        while(left<right)
        {
            if(*left==*right)left++,right--;
            else return false;
        }
        return true;
    }
    string longestPalindrome(string s) 
    {
        //法一（暴力解法）:O(N^3)
        // int len=0;
        // char* ter_left=&s[0],*ter_right=&s[0];
        // for(int left=0;left<s.size();left++)
        // {
        //     for(int right=left+1;right<s.size();right++)
        //     {
        //         if(is_reverse(&s[left],&s[right]) && right-left>len)
        //         {
        //             len=right-left;
        //             ter_left=&s[left],ter_right=&s[right];
        //         }
        //     }
        // }
        // string ret;
        // while(ter_left<=ter_right)
        //     ret+=*ter_left,ter_left++;
        // return ret;

        //法二（中心拓展算法）：O(N^2)
        int i=0;//固定中心点
        int left=0,right=0,len=0;
        string ret;
        for(int i=0;i<s.size();i++)
        {
            //1.求奇数长度
            left=i-1,right=i+1;
            int odd_len=1;
            while(left>=0 && right<=s.size() && s[left]==s[right])left--,right++,odd_len+=2;
            
            //2.求偶数长度
            int even_len=0;
            left=i,right=i+1;
            while(left>=0 && right<=s.size() && s[left]==s[right])left--,right++,even_len+=2;

            //3.判断是否更新ret
            if(odd_len>even_len && odd_len>len){
                ret=s.substr(i-(odd_len-1)/2,odd_len);
                len=odd_len;
            }
            if(even_len>odd_len && even_len>len){
                ret=s.substr(i-(even_len-2)/2,even_len);
                len=even_len;
            }
        }
        return ret;
    }
};